The reference in this specification to any prior publication (or information derived from it), or to any matter which is known, is not, and should not be taken as an acknowledgment or admission or any form of suggestion that that prior publication (or information derived from it) or known matter forms part of the common general knowledge in the field of endeavour to which this specification relates.
Typically, a digital camera user will take photos for one or more events and then download the photos from a memory card to a storage device (such as the hard disk of a PC or a Media Adaptor) and then archive it to a storage media such as a DVD or CD. Often, a user will only download the photos from a memory card when it becomes full.
Depending on the capacity of the memory card and whether the user is an ardent camera user or not, the downloaded photos may include events that span a few hours to a few months. Accordingly, as users start to accumulate a large collection of digital photos, searching and even browsing through the photos is no longer as enjoyable as it used to be. Additionally, users find it increasingly more difficult to recall the particular circumstances under which the photos were taken. Organising the photos before archiving them would help but organising even a few tens of photos is considered a tedious task by the average camera user.
A number of the more recent applications for managing photos have attempted to separate photos into time-based event clusters with various degree of success. Nevertheless, they typically divide the photos into a list of relatively short events and inevitably fail to recognise longer events as well as the relationship between long and short events. For example, a Europe Trip that is usually made up of shorter events such as a weekend at Paris, which in turn, can be made up of even shorter events such as a Moulin Rouge show.
Clustering of photos is typically performed using time-based event clustering. Most time-based event clustering techniques process the photos in chronological order creating new event clusters when the time gap (or interval) between neighbouring photos is greater than a certain threshold. The threshold may be a predetermined constant, a function of a windowed average of the time gaps between neighbouring photos of a current cluster or a function of the temporal extent of the current cluster. These methods create a single level of photo clusters. Some systems further partition the first level of photo clusters using content-based clustering into smaller sub-clusters of similar images, typically, by comparing the colour histogram of the images.
The problem with using a constant threshold on time gap is that such threshold does not work well on all photo sets. For instance, the events of a wedding are much shorter than the events of a vacation. Comparing the time gap against the average or extent of the time gap of a ‘current’ cluster ensures that the clustering is less dependent on the type of photo set. Nevertheless, the fact that existing algorithms always process photos in chronological order to create a single level of clusters means that the existence of an abnormally large time gap early in the construction of a ‘current’ cluster will easily result in a large cluster that misses all the smaller events.
Furthermore, content-based clustering using image features including the commonly used colour histogram, is far less reliable than time-based clustering. Hence, subsequent content-based sub-clustering of large clusters cannot satisfactorily correct errors caused by time-based event clustering.
Although production rules have been used to take into account of both temporal proximity and content similarity simultaneously when clustering photos, the use of crisp thresholds in such production rules do not allow the different criteria to be weighed and combined effectively, and consequently are very sensitive to boundary conditions.
Although hierarchical clustering of images for retrieval purposes, also exists, these algorithms typically perform content-based clustering by computing similarity measures over a set of image features and grouping similar images into clusters. A hierarchy of clusters can be formed by applying different image features to create new sub-clusters in a top-down manner or repeatedly combining similar clusters into larger intermediate clusters in a bottom-up manner. The use of content-based clustering instead of time-based event clustering in these methods means that these prior art differs substantially from the current invention.